#The TSP problem
#created by logan rooper- Riverdale High School - logan.rooper@gmail.com
#Random walk
import random
import math

################################################################################################
cycles = int(input("How many iterations do you want? >")) #INCREASE THIS TO INCREASE ITERATIONS#
num_cities = int(input("How many cites do you want? >")) #SET NUMBER OF CITIES
population = int(input("What population in the generations? Recommended: 50 >"))
################################################################################################

#Setting up the problem
print("Setting up the problem")
cities=[] #the regular city map
h_cities=[] #the highscore city map

#Generate num_cities random cities
#Cities should be in a X by Y array (0-9 coordinates
#Coordinates can be 101 through 199 (1 is the octal padding bit)
print("There are "+str(len(cities))+" cities.")

cities=(random.sample(range(100,199), num_cities))
for x in range(0,num_cities):
    print("Making city "+str(x)+".")
    print("City "+str(x)+" is X: "+str(cities[x])[1]+" and Y:"+str(cities[x])[2])

print("There are now "+str(len(cities))+" cities.")

#draw city map
print("PRINT MAP")

#iterate through all coordinates
row = ""
count = 1
for z in range(100,199):
    if z in cities:
        row += "--*--|"
    else:
        row += "-----|"
    if count == 9:                #rows is the width of the map...unsused because of our integer data limits
        row += "\n"
        count = 0
    count += 1

print(row)

print("Ready to create and run the algorithm??")
i = input(">")

#Create and run the algorithm
print("Creating/running the algorithm.")
high = 10000000.0 #arbitrarily high float value
done = False
i = 0

########ALGORITHM START##########
#create a list of paths (a generation)
generation = []
mid = []
sub = []
member = []
elite = []

'''GENERATION STRUCTURE  
             
generation[member_number] --> mid[0,1] --> sub[0xy]
                                           fitness
             &calling member's fitness is
                 generation[member_number][1]
             &a member's path item is
                 generation[member_number][0][i]
'''
fitness = 0
elite_fitness = 0
elite_data = []
#populate first generation with $population random induviduals
for x in range(0,population):
    #shuffle the member
    member = cities
    random.shuffle(member)
    #print(repr(member))
    #add the member's path to mid
    sub.insert(0,member)
    #calculate the member's fitness
    distance = 0
    for index, city in enumerate(member):
        cx = int(str(city)[1]) #currentX
        cy = int(str(city)[2]) #currentY
        if index != 0:
            #measure the absolute distance between c* and p* if it's not the first city
            distance += math.sqrt(abs((cx-px))**2+abs((cy-py))**2)
        px = cx
        py = cy
    
    fitness = 10/distance
    #find dat elite member and save him
    if fitness > elite_fitness:
        elite_fitness = fitness
        elite_data = member
    #add the member's fitness to mid
    sub.insert(1,fitness)
    mid.append(sub)
    
#push the member (mid) to generation
generation.insert(x,mid)
#print(repr(generation)) warning! takes forever...

#we now how our first generation, each member has values and fitnesses, and an elite member
#we now need to begin the full reprodcution loop, which takes a generation and returns a new generation
for x in range(0,cycles):
    #print("starting reproduction cycle "+str(x))
    #generate a pie for this generation: the pie determines the chance of being mate-selected
    pie = []
    for y in range(0,population):
        for y in range(0,len(generation[0])):
        pie.append(generation[0][0][
    for z in range(0,population):
        #print("mating event "+str(y))
        #select two members randomly and based on fitness
        
        


    





    
    if distance < high:
        high = distance
        h_cities = cities
        print("NEW HIGHSCORE FOUND ------------")
        print(repr(h_cities))
    i += 1
    if i >= cycles:
        done = True





#########ALGORITHM END###########
print("Shortest path found was "+str(high)+" units long.")
print()
print("PRINT MAP") #map of h_cities
print("--> X axis")
print("|")
print("| Y axis")
print("V")
row = ""
count = 1
for z in range(100,199):
    if z in h_cities:
        if cities.index(z) < 10:
            cit = "0"+str(cities.index(z))
        else:
            cit = str(cities.index(z))
        row += "--"+cit+"-|"
    else:
        row += "-----|"
    if count == 10:
        row += "\n"
        count = 0
    count += 1

print(row)

#EOF
